package com.leetcode.algorithm.y19.m03;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (TODO)114. 二叉树展开为链表
 * (done)116. 填充每个节点的下一个右侧节点指针
 * (done)117. 填充每个节点的下一个右侧节点指针 II
 * (done)958. 二叉树的完全性检验
 * (done)230. 二叉搜索树中第K小的元素
 * @author: jie.deng
 * @time: 2019年3月22日 下午2:35:46
 */
public class MySolution0322 {
	
	/**
	 * 114. 二叉树展开为链表
	 * 
     * 给定一个二叉树，原地将它展开为链表。
     * 
     * 例如，给定二叉树
     * 
     *     1
     *    / \
     *   2   5
     *  / \   \
     * 3   4   6
     * 将其展开为：
     * 
     * 1
     *  \
     *   2
     *    \
     *     3
     *      \
     *       4
     *        \
     *         5
     *          \
     *           6
	 * @param root
	 */
    public void flatten(TreeNode root) {
        
    }
    
    /**
     * 116. 填充每个节点的下一个右侧节点指针
     * 
     * 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
     * 
     * struct Node {
     *   int val;
     *   Node *left;
     *   Node *right;
     *   Node *next;
     * }
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     * 
     * 初始状态下，所有 next 指针都被设置为 NULL。
     * 
     *  
     * 
     * 示例：
     * 
     * 
     * 
     * 输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
     * 
     * 输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
     * 
     * 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
     *  
     * 
     * 提示：
     * 
     * 你只能使用常量级额外空间。
     * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
     * @param root
     * @return
     */
	public Node connect(Node root) {
		if (root == null || root.left == null || root.right == null) {
			return root;
		}
		root.left.next = root.right;
		root.right.next = root.next == null ? null : root.next.left;
		connect(root.left);
		connect(root.right);
		return root;
	}
   
    /**
     * 117. 填充每个节点的下一个右侧节点指针 II
     * 
     * 给定一个二叉树
     * 
     * struct Node {
     *   int val;
     *   Node *left;
     *   Node *right;
     *   Node *next;
     * }
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     * 
     * 初始状态下，所有 next 指针都被设置为 NULL。
     * 
     *  
     * 
     * 示例：
     * 
     * 
     * 
     * 输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":null,"next":null,"right":{"$id":"6","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
     * 
     * 输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}
     * 
     * 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
     *  
     * 
     * 提示：
     * 
     * 你只能使用常量级额外空间。
     * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
     * @param root
     * @return
     */
	public Node connectII(Node root) {
		if (root == null) {
			return null;
		}
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			Node pre = null;
			int size = queue.size(); // 当前层次结点个数
			for (int i = 0; i < size; i++) {
				Node node = queue.poll();
				if (i > 0) {
					pre.next = node;
				}
				pre = node;
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
		}
		return root;
	}
    
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val,Node _left,Node _right,Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };
    
    /**
     * 958. 二叉树的完全性检验
     * 
     * 给定一个二叉树，确定它是否是一个完全二叉树。
     * 
     * 百度百科中对完全二叉树的定义如下：
     * 若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）
     * 
     * 示例 1：
     * 输入：[1,2,3,4,5,6]
     * 输出：true
     * 解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。
     * 
     * 示例 2：
     * 输入：[1,2,3,4,5,null,7]
     * 输出：false
     * 解释：值为 7 的结点没有尽可能靠向左侧。
     * 
     * 提示：
     * 树中将会有 1 到 100 个结点。
     * @param root
     * @return
     */
	public boolean isCompleteTree(TreeNode root) {
		if (root == null) {
			return true;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			if (node == null) {
				// 遇到了第一个空结点，如果queue中有非空结点，则非完全二叉树
				while (!queue.isEmpty() && (node = queue.poll()) == null);
				return node == null;
			}
			queue.offer(node.left);
			queue.offer(node.right);
		}
		return true;
	}
    
    /**
     * 230. 二叉搜索树中第K小的元素
     * 
     * 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
     * 
     * 说明：
     * 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
     * 
     * 示例 1:
     * 
     * 输入: root = [3,1,4,null,2], k = 1
     *    3
     *   / \
     *  1   4
     *   \
     *    2
     * 输出: 1
     * 示例 2:
     * 
     * 输入: root = [5,3,6,2,4,null,null,1], k = 3
     *        5
     *       / \
     *      3   6
     *     / \
     *    2   4
     *   /
     *  1
     * 输出: 3
     * 进阶：
     * 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {
		List<Integer> list = new ArrayList<Integer>();
		TreeNode cur = root;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			if (!stack.isEmpty()) {
				cur = stack.pop();
				list.add(cur.val);
				cur = cur.right;
			}
		}
		return list.get(k-1);    	
    }
}
